Defragmenting the Module Layout of a Partially Reconfigurable Device

摘要

Modern generations of field-programmable gate arrays (FPGAs) allow forpartial reconfiguration. In an online context, where the sequence of modules tobe loaded on the FPGA is unknown beforehand, repeated insertion and deletion ofmodules leads to progressive fragmentation of the available space, makingdefragmentation an important issue. We address this problem by propose anonline and an offline component for the defragmentation of the available space.We consider defragmenting the module layout on a reconfigurable device. Thiscorresponds to solving a two-dimensional strip packing problem. Problems ofthis type are NP-hard in the strong sense, and previous algorithmic results arerather limited. Based on a graph-theoretic characterization of feasiblepackings, we develop a method that can solve two-dimensional defragmentationinstances of practical size to optimality. Our approach is validated for a setof benchmark instances.